The invention related to the field of telecommunications. More specifically the invention relates to a stuffing filter mechanism for data transmission signals.
With the advent of the Internet and the World Wide Web (WWW), the need for high-speed transmission of data including video and audio has continued to increase. Moreover, in addition to the demand for higher bandwidth, there has also been an increased need for various types of services that employ different protocols. For example, certain customers (e.g., companies providing voice services) of high-speed networks want to operate on a Time Division Multiplexing (TDM) Network, which combines different data streams, such as voice traffic, such that each data stream is assigned a time slot within the combined data stream. Moreover, other customers of high-speed networks may desire to transport data employing packet-based data streams, which do not have dedicated timeslots to given packets. Examples of the types of packets that can be placed into such data streams can include Asynchronous Transfer Mode (ATM), Internet Protocol (IP), Frame Relay, voice over IP and Point-to-Point Protocol (PPP).
Typically, such data transmission systems incorporate a larger number of data streams together into a single data stream to employ a greater percentage of the bandwidth of the transmission lines being employed. For example, under current data transmission standards 28 Data Signals (DS)1s are incorporated to form a DS3, thereby forming one signal that includes a number of smaller signals therein. Different network elements within these data transmission systems will break down such DS3 signals to extract all or a portion of the DS1 signals contained therein. Accordingly, these network elements can repackage the extracted DS1 signals with other DS1 signals to form other DS3 signals for subsequent transmission in the network. Further, such DS1 signals can be extracted to allow for the processing of the payload contained therein. For example, if a given DS1 signal may be carrying IP packets in the payload. These IP packets can be extracted from the payload and forwarded to their intended destination based on forwarding tables.
Currently, the bit rate of DS1 signals meets tight requirements of both the average bit rate and the bit-to-bit timing variations, known as xe2x80x9cjitter.xe2x80x9d However, the bit rate of the DS3 signal in which the DS1 signals are embedded is not required to meet such tight standards. Moreover, the bit rate of the DS3 signal is not required to have a close relationship to that of the DS1 signals it contains. Instead, bit rate variations between each DS1 signal and the containing DS3 signal are accommodated by xe2x80x9cbit stuffing.xe2x80x9d
As the DS1s are packed into the DS2s (which will be further packed to form the DS3), the DS2 data format provides occasional opportunities to make a decision to send a data bit or a xe2x80x9cnonsensexe2x80x9d bit (called a xe2x80x9cstuff bitxe2x80x9d). Stuff bits are discarded when the DS1 is eventually unpacked by the receiving network element, thereby leaving the data bits of the DS1 signal. Moreover, typically, the incoming data bits will be placed into a First In First Out (FIFO) (i.e., an elastic store) of the network element as they arrive and are extracted from the FIFO as the time to send the data bits occurs. At a time a decision to send a data bit or a stuff bit occurs, such a decision can be made on the basis of the number of data bits in the FIFO. A typical approach is to transmit data bits when the FIFO is greater than halfway full and to transmit a stuff bit if the FIFO is less or halfway full.
Due to such factors as the stuffing and destuffing steps, the layout of the data bits in the data formats and the jitter on the transmission path, the data bits that are unpacked from a DS3 often times arrive at a rate that is not smooth and/or constant.
One current technique to smooth out this DS1 bit rate is to employ phase lock loop analog circuitry. Such circuitry provides for a clock recovery that follows the average rate for a given transmission signal through the generation of a fresh clock from feedback circuitry based on the bit rate of the incoming DS1 signals. Moreover, the feedback circuitry can be based on the depth of the First In First Out (FIFO) containing extracted bits from the DS1 signal. With regard to the feedback circuitry based on the FIFO depth, the phase lock loop analog circuitry attempts to keep the FIFO approximately one-half full. Therefore, when the number of bits within the FIFO is greater than one-half, the rate is increased, and when the number of bits within the FIFO is less than one-half, the rate is decreased. While such analog circuitry allows a smooth egress rate, such circuitry is required to run continuously to allow for accurate calculations by the circuitry.
Moreover, the real estate that this analog circuitry would encompass is very expensive. In particular, a given traffic or line card within network elements in high speed networks are processing a large amount of data on a large number of channels, wherein each channel is associated with a different DS1 signal. Therefore, this phase lock loop analog circuitry would need to be replicated for each channel that a given line card processes. Line cards can currently process close to 700 channels, thereby requiring close to 700 phase lock loop analog circuits in order to allow for the continuous updating of the egress rate. Moreover, the demand for the number of such channels that line cards can process will continue to increase in the future, thereby increasing the amount of real estate on the line cards needed for phase lock loop analog circuitry.
Another conventional approach to smooth out this egress rate would be to provide digital circuitry that approximates the above described phase lock loop analog circuitry. However, in order to provide this smoothing out for each of the channels being received, such digital circuitry would need to run several times faster than the rate of a given channel. If a given channel is a DS1 signal, which has a rate of approximately 1.5 Megabits/second, this digital circuitry would need to be running as high as 8, 16 or 32 times such rate.
Smoothing, in some form, is necessary when a network element that extracts the DS1 signal must output this signal as a smooth, regular bit stream. If the DS1 signal is to be terminated and have its payload extracted within the network element, which extracted the DS1 from the DS3 signal, smoothing can, at times, be dispensed. However, in some network elements, a DS3 signal may be disassembled so that some or all of its component DS1s can be reassembled into a new DS3 signal for further transmission.
A current approach is to smooth the data rate of each extracted DS1 and then repack the DS1 into the DS3 signal as if the DS1 had arrived within the network element with a smooth, regular bit timing. Another approach would be to attempt to eliminate the smoothing step by combining the arrival and departure FIFOs, thereby making the stuffing decisions without first smoothing the bit arrival times for the DS1s. Unfortunately, without some smoothing, the timing irregularities accumulate with each unpack/repack step. Accordingly, the bit arrival times eventually become too irregular to meet network standards. Therefore, current techniques smooth the bit arrival times of the DS1s as they are unpacked from and repacked into DS3 signals.
Accordingly, there is a need to provide a mechanism and technique to smooth out the data rate of a large number of DS1 signals being packed into and/or extracted from a number of DS3 signals within network elements of high-speed communications networks.
A method and apparatus for performing bit stuffing operations for transmission signals are described. In an embodiment, a method includes receiving data for a number of channels of a signal. The method also includes recursively processing the data for the number of channels in an order. The processing of a channel of the number of channels includes retrieving a previous state for the channel upon determining that a timeslot for the channel is being processed. The previous state includes a history of values of a depth of a First In First Out (FIFO) for the channel. Moreover, the processing of the channel of the number of channels within the signal includes determining whether to make a bit stuffing decision for the channel upon determining whether the timeslot is associated with a bit stuffing opportunity for the channel. The bit stuffing decision is based on a current value and the history of the values of the depth of the FIFO for the channel. The method also includes updating a current state for the channel of the number of channels. Moreover, the current state for the channel of the number of channels within the signal is stored as the previous state for the channel.